/**
 * @author LKQ
 * @date 2022/2/23 22:54
 * @description 计数排序
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 寻找数组最大值
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        // 统计arr1中数字出现次数
        int[] frequency = new int[upper + 1];
        for (int x : arr1) {
            ++frequency[x];
        }
        int[] ans = new int[arr1.length];
        int index = 0;
        for (int x : arr2) {
            // 依照arr2中元素顺序，加入到ans中
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
            // 加入后置0
            frequency[x] = 0;
        }
        for (int x = 0; x <= upper; ++x) {
            for (int i = 0; i < frequency[x]; ++i) {
                // 没有出现在arr2中的数字
                ans[index++] = x;
            }
        }
        return ans;
    }
}
